import Data.List (iterate, findIndex)

unwrap :: Maybe a -> a
unwrap (Just v) = v

type Cup = Int
type Circle = [Cup]

step :: Circle -> Circle
step circle = circle'
    where
        curCup = head circle

        pickupCups = take 3 . tail $ circle
        dropedCircle = curCup : (drop 4 circle)

        max = maximum circle
        min = minimum circle

        next :: Cup -> Cup
        next cup = if cup == min then max else cup - 1

        destination = head . filter (not . (\c -> elem c pickupCups)) . iterate next $ (next curCup)

        destIndex = unwrap . findIndex (==destination) $ dropedCircle

        insertedCircle = (take (destIndex + 1) dropedCircle) ++ pickupCups ++ (drop (destIndex+1) dropedCircle)

        circle' = (tail insertedCircle) ++ [head insertedCircle]

order :: Circle -> Circle
order circle = (drop (pos1+1) circle) ++ (take pos1 circle)
    where
        pos1 = unwrap . findIndex (==1) $ circle

main :: IO ()
main = do
    let circle = [1,6,7,2,4,8,3,5,9]
    print . order . last . take 101 . iterate step $ circle